\subsection{Strategia evolutiva: l'algoritmo KGA} \label{sec:kga_intro}

L'algoritmo KGA \`e relativamente semplice: prende in considerazione una \textbf{popolazione} di $N$ individui in cui ciascun individuo rappresenta una possibile soluzione al problema, cio\`e le coordinate dei centroidi, indicate secondo una qualche codifica stabilita a priori (che verr\`a descritta poco pi\`u avanti). Di generazione in generazione la popolazione si evolve, favorendo gli individui con la fitness pi\`u alta (seguendo il principio secondo cui sopravvivono gli individui \textbf{pi\`u adatti}) e generando di volta in volta nuovi individui nati dallo scambio di materiale genetico tra i componenti della popolazione tramite le operazioni di \textbf{crossover} e \textbf{mutazione}.

L'algoritmo opera attraverso una serie di iterazioni, e una serie di step per ciascuna di esse: come prima cosa, ciascun cromosoma viene codificato e la posizione dei centroidi viene aggiornata applicando l'algoritmo K-means. Quindi viene calcolato il valore di \textit{clustering metric} $\mathcal{M}$ secondo la formula

\[
\mathcal{M} = \sum_{i=1}^K \sum_{\mathbf{x}_j \in C_i}  || \mathbf{x}_j - \mathbf{z}_i ||.
\]

$\mathcal{M}$ \`e dunque la somma delle distanze di ciascun punto del dataset dal centroide a cui \`e stato assegnato nel passaggio precendente.

Infine viene generata una popolazione di nuovi individui tramite le operazioni di selezione, mutazione e crossover. L'algoritmo termina dopo un numero prefissato di iterazioni\footnote{Alternativamente si sarebbe potuto pensare di richiedere che venisse raggiunto un certo valore di fitness media, o che almeno un individuo raggiungesse un certo valore di fitness.}.

\subsubsection{Le classi}

Le classi principali usate sono tre: \textbf{Chromosome}, \textbf{Population} ed \textbf{Evolution}. 

% La prima e la seconda rappresentano rispettivamente il singolo cromosoma e la popolazione di individui, mentre la terza contiene i metodi che controllano il processo evolutivo della popolazione.

La classe \textbf{Chromosome} rappresenta il singolo cromosoma, in cui gli alleli sono rappresentati tramite una lista di dimensioni $D \times K$. Essa offre una serie di metodi ausiliari che permettono di decodificare ``al volo'' i singoli centroidi (viene restituito un array D-dimensionale), di calcolare il valore di clustering metric e di applicare l'operatore di mutazione.

La classe \textbf{Population} descrive l'insieme d'individui che compongono la popolazione presa in esame, e offre i metodi per l'operazione di selezione, compreso l'ordinamento dei cromosomi in base al loro valore di fitness (necessario per la selezione di rango). Nel metodo \texttt{getNextGeneration} compare chiaramente il flusso descritto nella sezione \ref{sec:kga_intro}.

La classe \textbf{Evolution} \`e stata creata allo scopo principale di controllare tutti i parametri strettamente legati al processo evolutivo, come la probabilit\`a di mutazione e di crossover. Il metodo \texttt{evolve} infatti si limita a chiamare di volta in volta il metodo \texttt{getNextGeneration} e ad aggiornare il grafico (a patto che l'aggiornamento in real-time sia stato abilitato durante il setup).

% da continuare

\subsubsection{La codifica dei cromosomi}

Un aspetto fondamentale di un algoritmo genetico \`e la scelta della codifica dei cromosomi, in quanto questo influir\`a significativamente sul funzionamento degli operatori di mutazione e crossover. In questo caso, anzich\'e una codifica binaria, si \`e optato per l'utilizzo di una serie di numeri reali disposti in modo che, in un dominio $D$-dimensionale, i primi $D$ numeri rappresentano le coordinate del primo centroide, i successivi $D$ le coordinate del secondo e cos\`\i\ via. Il numero di \textit{alleli} per ciascun cromosoma \`e quindi dato da $K \times D$, dove $K$ \`e il numero di centroidi\footnote{Come specificato in precedenza, questo numero viene stabilito a priori.}. Nel caso ad esempio di $D = 2$ e $K = 3$ un cromosoma avr\`a quindi la forma

\[
C = a_x^1a_y^1a_x^2a_y^2a_x^3a_y^3
\]

\subsubsection{Calcolo di \textit{metric} e \textit{fitness}}

Dal momento che l'algoritmo KGA nasce nel contesto dei problemi di clusterizzazione, il valore della fitness di ciascun cromosoma deve rispecchiare quanto quella particolare disposizione di centroidi rappresenta efficacemente la disposizione dei raggruppamenti di punti del dataset fornito. Come spiegato in precedenza, ad ogni ciclo viene calcolato il valore $\mathcal{M}$ di clustering metric, che d\`a esattamente una misura di questa caratteristica: questo valore viene salvato nella struttura dell'oggetto Chromosome e la fitness \`e definita come $\frac{1}{M}$.

\subsubsection{Selezione, mutazione e crossover}

L'operazione di selezione avviene tramite selezione di rango: i cromosomi vengono ordinati in base a valori crescenti della loro fitness tramite il metodo \texttt{getSortedFitnessList} della classe \textit{Population} e ciascuno di essi viene selezionato con una probabilit\`a che \`e proporzionale alla loro posizione nella lista. In questo modo non si rischia di favorire eccessivamente un cromosoma avente un valore di fitness particolarmente elevato rispetto alla media a scapito di altre soluzioni che potrebbero contenere materiale genetico utile per il ritrovamento dell'ottimo globale.

In questo caso la mutazione funziona in modo sensibilmente diverso rispetto a quando visto nell'algoritmo SGA con cromosomi a codifica binaria: se in quel caso infatti l'effetto dell'operatore era quello di invertire ogni \textit{bit} di ogni cromosoma con probabilit\`a \textit{pmut} ad ogni iterazione, nell'algoritmo KGA il meccanismo \`e pi\`u complesso. Innanzitutto il cambiamento che avviene sul singolo cromosoma dipende dal suo valore di clustering metric in relazione con i valori massimi e minimi trovati tra tutta la popolazione: gli individui aventi i valori \textbf{minimi} (cio\`e i migliori) non subiranno mutazione, viceversa gli individui peggiori saranno maggiormente influenzati, \`e presente dunque una forma di preservazione dell'individuo migliore. Esiste altres\`\i\ un sistema per prevenire la stagnazione: il grado di mutazione diventa massimo per tutti i cromosomi nel momento in cui tutti gli individui hanno lo stesso valore di clustering metric.

Per via del modo in cui funziona questo operatore, \`e possibile portare il valore della probabilit\`a di mutazione a valori decisamnete pi\`u alti rispetto a quelli usati con SGA, dal momento che non si rischia di far allontanare troppo gli individui migliori dalle posizioni ottime trovate in precedenza. Per ulteriori dettagli sul meccanismo di mutazione, consultare \cite{KGA}.

Il crossover viene eseguito, con una probabilit\`a stabilita in fase d'inizializzazione, nella stessa maniera rispetto all'algoritmo SGA: selezionati due cromosomi viene scelto un numero intero $p$ compreso tra 1 e $L-1$, dove $L$ \`e la lunghezza del cromosoma (il numero di alleli da cui \`e composto) pari a $D \times K$. Quindi il primo dei due nuovi cromosomi viene creato prendendo i primi $p$ alleli dal \textbf{primo} cromosoma e i restanti dal \textbf{secondo}, viceversa il secondo discendente eredita i primi $p$ alleli dal \textbf{secondo} cromosoma e gli altri dal \textbf{primo}.
